package com.tgy.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * https://leetcode-cn.com/problems/subsets-ii/
 *
 * 输入：nums = [1,2,2]
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 *
 * 1,2,2
 * 1,2,
 * 1,
 * 2,2
 * 2,
 * 2
 * []
 *
 * [1,2,3]
 * 123
 * 12
 * 1
 * 23
 * 2
 * 3
 *
 * [1,1,1]
 *
 * 1,1,1
 * 1,1
 * 1,
 */

public class _90_子集_II {

    public static List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();

        ArrayList<Integer> container = new ArrayList<>();
        doSubsets(nums,0, container, res,false);
        return res;
    }

    public static void doSubsets(int[] sortNums,int index, List<Integer> container, List<List<Integer>> res, boolean select){

        if (index >= sortNums.length) {
            res.add(new ArrayList<>(container));
            return;
        }
        container.add(sortNums[index]);
        doSubsets(sortNums,index+1,container,res,true);
        container.remove(container.size() - 1);

        if (!select && index > 0 && sortNums[index - 1] == sortNums[index]) {

            return;
        }

        doSubsets(sortNums,index+1,container,res,false);

    }

    public static void main(String[] args) {

        int[] nums = {1,2,2};
        List<List<Integer>> res = subsetsWithDup(nums);
        for (List<Integer> re : res) {
            System.out.println(re);
        }

    }
}
